\chapter{Model} \label{chap:model}
The solution to the Micromanagement problem will be Potential Fields that are tuned by a multi-objective genetic algorithm (MOGA). The Micromanagement techniques presented in Chapter \ref{chap:domainmechanics} are the basis for the solution. 

Since the solution is complex the explanation will be divided into parts addressed separately. The solution is an expansion of the ideas from \citet{hagelbackmulti} and \citet{sandberg2011evolutionary}, using MOGA to optimize instead of GA. 

\section{AI Overview}
\label{sec:ai_overview}
The AI will be in one of two possible modes when playing. The \textit{training mode} is for evolving solutions with a GA, and the \textit{testing mode} is for running a match with a manually set solution. This section will focus mainly on the training mode and this is this mode that is used for finding the final solution.

At the beginning of a match the AI will have a genome that represents a set of weights used in the Potential Field functions, these weights will be used for the entirety of the match and the purpose of the match will be to test how well the AI performs with the given weights. This means that during training, as the AI will pick different weights, the AI's behaviour will only change between matches. How these weights and their Potential Fields decide the actions of the controlling units is explained in Section~\ref{sec:model_pf}.

In training mode each StarCraft match is a fitness test. The data that is used to decide the fitness is gathered both during and at the end of the match, and then used in the fitness functions (see Section~\ref{sub:functions}). This means that during training the set of weights represented by the genome will evolve, and the average individuals behaviour change.

\begin{figure}[h]
	\centering
	\includegraphics[width=\linewidth]{img/ai_overview.png}
	\caption{Overview of the AI in training mode.}
	\label{fig:ai_overview}
\end{figure}

While in testing mode the AI performs quite similarly to the testing mode shown in Figure~\ref{fig:ai_overview}, except that it disconnects the evaluating and evolving part, and has a manually set weight array. This means that its behaviour will never change between matches. The testing mode will be used for the experiments.

\section{Potential Fields}
\label{sec:model_pf}
The algorithm will decide in which direction a unit will move or who to attack based on the Potential Field functions. They will output a value that represents a direction or a target, and is translated by the algorithm into a StarCraft command. The purpose of the Potential Fields is to execute the techniques presented in Section~\ref{sec:micromanagement}.

Every unit you control will have their own Potential Fields which means they have to be calculated for each unit. This is in contrast to \citet{hagelbackmulti} who have the same Potential Fields for all groups of units. The fields will be placed on all enemy units in sight and at the center of the group (COG) of soldiers you control. The fields on the enemy units are for deciding who to attack and deciding in which direction to retreat. The fields placed at the center of the group are for directing the unit towards other friendly units when retreating. The Potential Fields will be updated several times each second because the environment in StarCraft is highly dynamic and fast paced.

\todo{Lag figur som viser eksempel på pf'ene våre.} 

\subsection{Functions} \label{sub:functions}
The functions decide how strong a field is. There are three potential fields: One for enemy units when not on cooldown, one for enemy units when on cooldown, and one for the center of squad.

There are different fields depending on whether it is for an enemy unit, COG, or if the unit is on cooldown. The functions use the properties and variables presented in Section \ref{sec:attributes}. \citet{sandberg2011evolutionary} inspired the general style of the functions, especially the dependence on Maximum Shooting Distance (MSD), but they are quite different because the placement is different. Also there are fewer types of Potential Fields (only three), because this approach to the Micromanagement problem is different. There is more focus on Micromanagement techniques and less on general Micromanagement in the solution in this thesis. \todo{Why?}

The functions will use the following terminology:
\begin{description}
  \item[$force$] The total attraction/repulsion exerted from one Potential Field.
  \item[$distance$] The distance from the enemy unit.
  \item[$MSD$] The maximum shooting distance of the unit.
  \item[$eMSD$] The maximum shooting distance of the enemy unit.
  \item[$HP$] The unit's HP.
  \item[$eHP$] The enemy unit's HP.
  \item{$HP_{max}$} The maximum amount of HP a unit can have.
  \item[$w_n$] A weight.
  \item[$max(x,y)$] The greater of \textit{x} and \textit{y}.
\end{description}
	
\begin{equation}\label{eq:attracting}
force_{attack} = w_3 * (1 - \frac{eHP}{eHP_{max}}) + w_4 * \frac{1}{distance} 
\end{equation}

Equation~\ref{eq:attracting} shows the function used when the unit is not on cooldown. In this mode the Potential Fields around enemy units will have an attracting force, and the unit with the highest attractive force is attacked. It is necessary that only the strongest field is the one that affects the movement of the unit to achieve focus firing. Because if a unit in StarCraft is commanded to attack in a direction it will automatically attack the closest one, but to achieve effective focus fire one will want to, at times, attack other units than the closest one.

\begin{equation} \label{eq:repelling}
force_{escape}= \begin{cases}
 w_0*distance & if (distance - max(MSD, eMSD) + w_2 * (1 - \frac{HP}{HP_{max}}) > 0)\\
-\frac{w_1}{distance} & else
\end{cases}
\end{equation}

Equation~\ref{eq:repelling} shows the function for the field emitted by an enemy unit when a friendly unit is on cooldown. The force of the field is repulsive if you are inside the enemy unit's maximum shooting distance in addition to a threshold, and attractive while outside. The result is that the unit is kept a certain distance outside the enemy unit's MSD, so that it can avoid being attacked by the enemy unit while being able to move in for the attack as soon as the cooldown is over. Because of this it is desirable that this distance is short, but not so short that the unit cannot escape. 

\begin{equation}\label{eq:cog}
force_{CoG} = w_5
\end{equation}

Equation~\ref{eq:cog} shows the function used for the COG Potential Field. It is only active while on cooldown, because attacking takes priority when the unit able to attack. However when on cooldown all the forces are summed to decide the direction of where the unit should move. The COG Field is used to guide the unit towards the other friendly units, which is a part of the positioning challenge. If gathered together units have less of a chance to be picked off. The field is constant and only dependent on the weight, which represents the importance of moving towards the COG.

Before implementing the functions they were simulated in Excel to see if the functions created the desirable Potential Fields.

\todo{Grafer fra Excel eller noe lignende.}

\section{NSGA-II}
NSGA-II will be used to tune the weights used in the Potential Fields functions. Because of the complexity of the problem (defined in Section~\ref{sec:rq}) several objectives are needed, and multi-objective optimization is a good way to solve problems with multiple objectives \citep{coello2007evolutionary}. It is also a way for us to improve upon the solution presented in Subsection~\ref{sec:EMAPF}.

The objectives represent how well the AI performs the Micromanagement techniques. These behaviours are: positioning, focus firing retreating and staying alive as discussed in Section~\ref{sec:micromanagement}. The NSGA-II algorithm will optimize the PF functions' weights using fitness functions based on the objectives. Parameters like mutation rate and population size will be tuned manually.

\subsection{Objectives} \label{sub:objectives}
The objectives are:
\begin{description}
 \item[Focus firing] attacking a weaker unit.
 \item[Positioning] moving the units to their optimal positions.
 \item[Tactical retreating] moving away from enemy firing range when on cooldown.
 \item[Staying alive] retreating more further when unit's HP is low.
\end{description}

Representing the objectives directly in fitness functions is not feasible, but implicitly doing so is possible. The resulting fitness functions reward one or several of the objectives at once, but care has been taken to make sure they are not overlapping more than necessary.\todo{explain?} There has also been an attempt to make them as generic as possible to allow for new behaviours. There are a total of four fitness functions who focus on different parts of the performance. 

\begin{equation}\label{eq:cog}
fitness_{KS} = \frac{\sum_{n=0}^{noKilledUnits} valueUnit_n - \sum_{n=0}^{noLostUnits} valueUnit_n}{ \sum_{n=0}^{noEnemyUnits} valueUnit_n * 2}
\end{equation}

The killscore ($fitness_{KS}$) is a value calculated by StarCraft at the end of each match. It is based on how many units lost compared to units lost by the opponent, and takes into account the relative strength of each unit, giving a higher score to units who are stronger. $n$ represents a unit, identified by a number between 0 and the total number of killed or lost units. $valueUnit$ is the value of the unit. Because the total value of the enemy units and the total value of the friendly units is not necessarily the same, the value range of $fitness_{KS}$ varies according to what units are fighting.  

The killscore awards all the objectives and is a general measure of good Micromanagement. Focus firing is rewarded because focus firing kills enemy units faster than not focus firing. The other objectives are based on survivability and surviving means loosing fewer units. 

\begin{equation}\label{eq:cog}
fitness_{HP} = \frac{\sum_{n=0}^{noUnits}\frac{HP_{n}}{max(HP_n)}}{noUnits}
\end{equation}

The HP fitness ($fitness_{HP}$) is the average HP remaining at the end of the match divided by the maximum HP possible. $HP_n$ is the HP of unit $n$ and $max(HP_n)$ is the highest HP the unit can have. The fitness is a measure of how many hits the units have taken and especially rewards tactical retreating. Of course, it is a general reward as all the fitness functions give off bad values given a loss. The HP fitness will output 1 if no friendly units took any damage during the match. If the match was lost, the fitness will return the remaining enemy units' HP as a negative value, resulting in -1 if no damage was dealt by the friendly units.

\begin{equation}\label{eq:cog}
fitness_{FF} = \frac{\sum_{n=0}^{noUnits}\frac{damage_n}{max(damage_n)}}{noUnits}
\end{equation}

The focus fire fitness ($fitness_{FF}$) function takes the current damage output and divides it on the maximum damage output possible up to this point. $damage_n$ is the damage a unit $n$ has done this far. The result will be between 0 and 1 and represent how large a percentage of the total possible damage the group of units have done.  

This fitness function rewards attacking as often as possible, and though it does not reward focus firing explicitly it is likely to boost it because it makes sure everyone attacks. When everyone attacks focus firing is more likely to occur. Non-attacking unit will be heavily punished by this function. There is no explicit focus fire fitness function, but it is encouraged in the PF functions, and if it is a useful tactic it will be rewarded because fewer units die.

\begin{equation}\label{eq:cog}
fitness_{SA} = \frac{\sum_{n=0}^{noUnits}\frac{timeAlive_n}{max(time)}}{noUnits}
\end{equation}

The last fitness function records how long a unit managed to stay alive in relation to the total time. It is averaged over all units because it is the performance of the group as a whole that is relevant. Focus firing, positioning and staying alive is only effective if two or more units are cooperating. \todo{Write about why?} The fitness function rewards survivability and is meant to promote moving back while hurt and let other units with more HP take damage, as well as positioning correctly when on cooldown.  

\subsection{Genome Representation}
The genotypes in the population are normalized bitstrings. Since the different PF weights will have different proportions as described in the previous subsection, the decoding algorithm has a set of parameters telling it the range and number of bits dedicated to each of the chromosomes. E.g. one weight might have the range [0.10] represented by 8 bits, which will allow it to differentiate up to circa 0.04 accuracy.

\subsection{Evolutionary Operators}
For the NSGA-II implementation mutation, single-point crossover and binary tournament selection was used. Mutation is done on the individual-level, meaning that an individual has one chance for one of its genes to be mutated and nothing more. Crossover has one chance in the breeding process to do a single-point crossover, if this occurs a random point between the chromosomes is chosen and recombination is done on two parents to create two recombined children as Figure~\ref{fig:crossover} shows.